﻿using System;
using System.CodeDom;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Security.Authentication.ExtendedProtection;
using System.Text;
using System.Threading.Tasks;

namespace ChineseRemainderTheorem.Core
{
    public class SecretSharingService : ISecretSharingService
    {
        #region Fields

        private readonly IBigIntegerRandom _bigIntegerRandom;

        #endregion

        #region Constructors

        public SecretSharingService(IBigIntegerRandom bigIntegerRandom)
        {
            if (ReferenceEquals(bigIntegerRandom, null))
            {
                throw new ArgumentNullException("bigIntegerRandom");
            }
            _bigIntegerRandom = bigIntegerRandom;
        }

        #endregion

        #region Methods

        public SecretSharingOperation[] Share(BigInteger secret, int usersToRestoreCount, int totalUserCount)
        {
            // generate prime number p > M
            BigInteger p;
            while (!_bigIntegerRandom.NextPrime(secret, secret*2, out p)) { }

            // строим многочлен вида (А(k) * x^k + A(k-1) * x^(k-1) ... + A(1)*x + M) mod p
            // generate k-1 A(k) members
            BigInteger[] coefficients = new BigInteger[usersToRestoreCount - 1];
            for (int i = 0; i < coefficients.Length; ++i)
            {
                // less than secret
                coefficients[i] = _bigIntegerRandom.Next(secret);
            }

            // k-array
            SecretSharingOperation[] secretSharingOperations = new SecretSharingOperation[totalUserCount];
            for (int secretIndex = 1; secretIndex <= totalUserCount; secretIndex++)
            {
                BigInteger k = BigInteger.Zero;
                for (int j = 0; j < coefficients.Length; ++j)
                {
                    k += BigInteger.Pow(coefficients[j], coefficients.Length - j)*secretIndex;
                }
                k += secret;
                ModField.Normalize(ref k, p);
                secretSharingOperations[secretIndex - 1] = new SecretSharingOperation(k, secretIndex, p, usersToRestoreCount - 1);
            }

            return secretSharingOperations;
        }

        public Task<SecretSharingOperation[]> ShareAsync(BigInteger secret, int usersToRestoreCount, int totalUserCount)
        {
            return Task.Run(() => Share(secret, usersToRestoreCount, totalUserCount));
        }

        private BigInteger Restore(SecretSharingOperation[] secrets)
        {
            BigInteger mod = secrets.Select(s => s.Mod).First();

            List<BigInteger[]> ls = new List<BigInteger[]>(secrets.Length);
            for (int i = 0; i < secrets.Length; ++i)
            {
                IList<BigInteger> divisors = new List<BigInteger>(secrets.Length);
                IList<BigInteger> coeffs = new List<BigInteger>(secrets.Length);
                // IList<BigInteger> divisors = new List<BigInteger>(power + 1);
                // IList<BigInteger> coeffs = new List<BigInteger>(power + 1);

                // BigInteger[] coeffs = new BigInteger[secrets.Length - 1];
                for (int j = 0; j < secrets.Length; ++j)
                {
                    // if j == i - go to the next iteration
                    if (j == i)
                    {
                        continue;
                    }
                    // получаем все коэф, которые используем
                    coeffs.Add(-secrets[j].Index);
                    // calculate divisor
                    divisors.Add(secrets[i].Index - secrets[j].Index);
                }
                // создаем многочлен
                // вычисляем общий знаменатель и приводим его к виду поля вычетов (через нахождение обратного)
                // a/b mod p = a*(b^(-1) mod p) mod p
                // b^(-1) - мультипликативно обратный по модулю m
                // b * (b^(-1)) = 1 mod m
                BigInteger commonDivisor = divisors.Aggregate(BigInteger.One, (current, divisor) => current * divisor);
                ModField.Normalize(ref commonDivisor, mod);
                BigInteger multiplier = ModField.ReverseOnField(commonDivisor, mod);

                // вычисляем значения коэфициентов полинома при переменной x
                BigInteger[] polynomCoefficients = new BigInteger[secrets.Length], coeffsArray = coeffs.ToArray();
                polynomCoefficients[0] = 1;
                for (int j = 1; j < polynomCoefficients.Length; ++j)
                {
                    IEnumerable<List<BigInteger>> c = GetPowerCoefficients(coeffsArray, j);
                    polynomCoefficients[j] = c.Aggregate(BigInteger.Zero,
                        (current1, tuple) =>
                            current1 + tuple.Aggregate(BigInteger.One, (current, value) => current * value));
                }

                // normalize coeffs, multiply and normalize coeffs
                for (int j = 0; j < polynomCoefficients.Length; j++)
                {
                    polynomCoefficients[j] *= multiplier;
                    ModField.Normalize(ref polynomCoefficients[j], mod);
                }
                // add to L collection
                ls.Add(polynomCoefficients);
            }

            // можно вычислить все значения коэффициентов, которые использовались при разделении
            // значение последнего и будет искомым секретом

            // *** Не будем вычислять все, сразу вычислим последний ***
            // длина секрета должна совпасть с длинной количества выражений
            BigInteger result = BigInteger.Zero;
            for (int i = 0; i < secrets.Length; ++i)
            {
                result += secrets[i].Secret * ls[i][secrets.Length - 1];
            }
            ModField.Normalize(ref result, mod);
            return result;
        }

        public BigInteger Restore(SecretSharingOperation[] secrets, int usersToRestoreCount, int totalUserCount)
        {
            int power = secrets.Select(s => s.Power).First();

            if (power >= secrets.Length)
            {
                return BigInteger.Zero;
            }
            else
            {
                Random rand = new Random();
                // берем нужное количество случайных уравнений
                IList<int> indeses = secrets.Select(s => s.Index).ToList();
                SecretSharingOperation[] shards = new SecretSharingOperation[power + 1];
                for (int i = 0; i < shards.Length; ++i)
                {
                    // случайный индекс в массиве индексов
                    int indexIdx = rand.Next(0, indeses.Count - 1);
                    shards[i] = secrets[indeses[indexIdx] - 1];
                    indeses.RemoveAt(indexIdx);
                }
                return Restore(shards);
            }

        }

        public Task<BigInteger> RestoreAsync(SecretSharingOperation[] secrets, int usersToRestoreCount, int totalUserCount)
        {
            return Task.Run(() => Restore(secrets, usersToRestoreCount, totalUserCount));
        }

        private static IEnumerable<List<BigInteger>> GetPowerCoefficients(BigInteger[] values, int count)
        {
            if (count == 1)
            {
                foreach (BigInteger bigInteger in values)
                {
                    yield return new List<BigInteger> {bigInteger};
                }
            }
            else
            {
                if (count == values.Length)
                {
                    yield return new List<BigInteger>(values);
                }
                else
                {
                    int windowSize = count - 1;
                    for (int i = 0; i < values.Length - 1; ++i)
                    {
                        //int startIndex = i + 1;

                        //while (startIndex + windowSize <= values.Length)
                        //{
                        //    
                        //    startIndex++;
                        //}
                        for (int startIndex = i + 1; startIndex + windowSize <= values.Length; startIndex++)
                        {
                            List<BigInteger> result = new List<BigInteger> { values[i] };
                            ArraySegment<BigInteger> segment = new ArraySegment<BigInteger>(values, startIndex, windowSize);
                            result.AddRange(segment);
                            yield return result;
                        }
                    }
                }
            }
        }

        #endregion
    }
}
